package graph;

/**
 * O(n^3)
 * 
 * @author yinzichen
 * 
 */
public class Floyd {
	public int[][] floyd(int[][] g) {
		int n = g.length;
		int[][] graph = new int[n][n];
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < n; ++j)
				graph[i][j] = g[i][j];
		for (int u = 0; u < n; ++u) {
			for (int s = 0; s < n; ++s) {
				for (int t = 0; t < n; ++t) {
					if (graph[s][t] > graph[s][u] + graph[u][t]) {
						graph[s][t] = graph[s][u] + graph[u][t];
					}
				}
			}
		}
		return graph;
	}
}
